package com.aqie.medium.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 1079 字符串全排列个数
 * todo
 */
public class NumTilePossibilities {
    public int numTilePossibilities(String tiles) {
        Integer[] dict = new Integer[tiles.length()];
        for (int i = 0; i < tiles.length(); i++){
            dict[i] = (int)tiles.charAt(i);
        }
        // 深度优先遍历
        return dfs("", Arrays.asList(dict), new HashSet<>());
    }

    private int dfs(String word, List<Integer> dict, HashSet<Object> set) {

        int count = 0;
        // 如果 set 没有这个字符串word, 排列组合数 + 1
        if(word.length() != 0 && !set.contains(word)){
            set.add(word);
            count++;
        }

        // 遍历字典树
        for (int i = 0; i < dict.size(); i++){
            List<Integer> list = new ArrayList<>(dict);
            /**
             * 抽取一个字符串拼接到 word 字符串后面
             */
            int tmp = list.remove(i);
            count += dfs(word + tmp, list, set);
        }
        return count;
    }
}
